#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

void dtob(uint64_t num);                      //from decimal base to binary base
void dtopoly(uint64_t num);                   //from decimal base to polynomial
int gen(uint64_t a, uint64_t b);              //generate the next bit
void shift(uint64_t *a,uint64_t offset,int g);//shift the register
uint64_t deg(uint64_t poly);                  //return the degree of the polynomial


void dtob(uint64_t num)
{
  int a[64],c,i=0;
  if(num == 0) {
    printf("0b0");
  }
  else {
  printf("0b");
    while (num > 0)
      {
          c = (num % 2);
          a[i] = c;
          num = num / 2;
          i++;
      }
    for (i--; i >= 0; i--)           //reverse output
          printf("%d", a[i]);
  }
  printf("\n");
}

void dtopoly(uint64_t num)
{
  int a[64],c,i=0;
  if(num == 0) {
    printf("0");
  }
  else {
    while (num > 0)
      {
          c = (num % 2);
          a[i] = c;
          num = num / 2;
          i++;
      }
    bool toggle=1;
    for (i--; i > 1; i--)           //reverse output
    {
         if(a[i]==1&&toggle==1){printf("x^%d", i);toggle=0;}
         else if(a[i]!=0)printf("+x^%d", i);
    }
         if(a[1]==1&&toggle==1){printf("x");toggle=0;}
         else if(a[1]==1)printf("+x");
         if(a[0]==1&&toggle==1){printf("1");toggle=0;}
         else if(a[0]==1)printf("+1");
  }
}

int gen(uint64_t a, uint64_t b)
{
  uint64_t num = a & b;
  if(num == 0) {
    return 0;
  }
  else {
    int c=0;
    while (num > 0)
      {
          c = c + (num % 2);
          num = num / 2;
      }
    return(c%2);
  }
}

void shift(uint64_t *a,uint64_t offset,int g)
{
  *a = *a >> 1;
  if(g==1) {
    *a = *a ^ offset;
  }
//  dtob(*a);
}

uint64_t deg(uint64_t poly)
{
  uint64_t num=1;
  while(poly>>num)
  {
    num++;
  }
  return num-1;
}
